/*************************************************
 *	文件名称：mydataexample.c
 *	文件说明：本代码为mydataexample.h的函数实现，需要
			  和mydataexample.h一起编译
 *	程序平台：for linux
 *	文件作者：Jason <jasonsunsoft@163.com>
 *	文件时间：
*************************************************/

#include "mydata.h"

Status MakeNode(Link *p, ElemType e)
{
	(*p) = (Link) malloc(sizeof(LNode));
	if (*p)
	{
		(*p)->data = e;		//将数值传递给结点
		(*p)->next = NULL;	//将后继结点地址设置为空
		return OK;
	}
	else
		return ERROR;
}

void FreeNode(Link p)
{
	free(p);
}

Status LocateElem(LinkList L, ElemType e, Position *q, Status (*compare)(ElemType, ElemType))
{
	Link p, t;

	if (!L.len)
		return ERROR;
	p = L.head->next;
	t = L.tail;
	while (p != t)
	{
		if (compare(e, p->data))
			break;
		else
			p = p->next;
	}
	if (!compare(e, p->data))
	{
		*q = p;
		return OK;
	}

	else
	{
		*q = NULL;
		return ERROR;
	}
}

//已知h指向线性链表的头结点，将s所指结点插入在第一个节点之前
Status InsFirst(Link h, Link s)
{
	if ((!s) && (!h->next))
		return ERROR;
	s->next = h->next;
	h->next = s;
	return OK;
}//InsFirst

Status InitList(LinkList *L)
{
	L->head = (Link)malloc(sizeof(LNode));
	if (!(L->head))
		return ERROR;
	L->head->next = NULL;	//设置头结点的下一个结点为空
	L->tail = L->head;
	L->len = 0;
	return OK;
}//InitList

Link GetHead(LinkList L)
{
	return L.head;
}

//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
Status SetCurElem(Link p, ElemType e)
{
	p->data.coef = e.coef;
	p->data.expn = e.expn;
	return OK;
}

Status ClearList(LinkList *L)
{
	Link p, r;

	r = L->head->next;
	while (r)
	{
		p = r->next;
		FreeNode(r);
		r = p;
		L->len --;
	}
	if (L->len == 0)
	{
		L->head->next = NULL;
		L->tail = L->head;
		return OK;
	}
	else
		return ERROR;
}//ClearList_Sq

Position NextPos(LinkList L, Link p)
{
	Link q;

	if (p == L.tail)
		return NULL;
	q = L.head;
	while((q != p) && (q->next != NULL))
	{
		q = q->next;
	}
	if (q->next == NULL)
		return NULL;	//未找到p
	if (q == p)
		return q->next;
	return NULL;
}

void GetCurElem(Link p, ElemType *e)
{
	e->coef = p->data.coef;
	e->expn = p->data.expn;
}

Status DelFirst(Link h, Link *q)
{
	if (!h->next)
		return ERROR;
	*q = h->next;
	h->next = h->next->next;
	(*q)->next = NULL;
	return OK;
}

Status Append(LinkList *L, Link s)
{
	L->tail->next = s;
	while (L->tail->next)
	{
		L->tail = L->tail->next;
		L->len++;
	}
	return OK;

}

Position PriorPos(LinkList L, Link p)
{
	Link q;

	q = GetHead(L);
	if (q->next == p)
		return NULL;
	while((q->next != p) && (q->next != NULL))
	{
		q = q->next;
	}
	if (q->next == NULL)
		return NULL;		//未找到p
	if (q->next == p)
		return q;
	return NULL;		//我知道这里估计怎么也执行到的，为了看着舒服还是加上来了。
}





int cmp(term a, term b)
{
	if (a.expn < b.expn)
		return -1;
	else if (a.expn == b.expn)
		return 0;
	else
		return 1;
}



void CreatPolyn(polynomail * P, int m)
{
	Link h, s;
	ElemType e;
	Position q;
	int i;

	InitList(P);
	h = GetHead(*P);
	e.coef = 0.0;
	e.expn = -1;
	SetCurElem(h, e);	//设置头结点参数
	for (i = 1; i <= m; i++)
	{
		printf("plese enter item like 0.1 5 \n");
		scanf("%f %d",&e.coef, &e.expn);
		if (!LocateElem(*P, e, &q, cmp)) //当前链表中不存在该指数
		{
			q = P->head;
			if (MakeNode(&s, e))	//生成结点
				InsFirst(q, s);		//插入节点
			P->len ++;
			if (h == P->tail)		//设置尾结点
				P->tail = s;
		}
	}

}//CreatPolyn


void DestroyPolyn (polynomail *p)
{
	ClearList(p);
	FreeNode(p->head);
	free(p);

}

void PritPolyn(polynomail P)
{
	Link q;
	printf("multinomial have %d terms.\n", P.len);
	printf("multinomial is ");
	q = P.head->next;
	while(q != P.tail)
	{
		printf("%0.1f x^%d + ", q->data.coef, q->data.expn);
		q = q->next;
	}
	printf("%0.1fx^%d \n", q->data.coef, q->data.expn);
}

int PolynLenght(polynomail P)
{
	return P.len;
}

void AddPolyn(polynomail *Pa, polynomail *Pb)
{
	Link ha, hb;
	Position qa, qb;
	ElemType a, b;
	float sum;

	ha = GetHead(*Pa);
	hb = GetHead(*Pb);		//获取Pa, Pb的头结点。
	qa = NextPos(*Pa, ha);
	qb = NextPos(*Pb, hb);

	while (qa && qb)
	{
		GetCurElem(qa, &a);
		GetCurElem(qb, &b);
		switch (cmp(a, b))
		{
		case 1:
			ha = qa;
			qa = NextPos(*Pa, ha);
			break;
		case 0:
			sum = a.coef + b.coef;
			if (sum != 0.0)
			{
				qa->data.coef = sum;
				ha = qa;
			}
			else
			{
				DelFirst(ha, &qa);
				if (!ha->next)
					Pa->tail = ha;
				Pa->len --;
				FreeNode(qa);
			}
			DelFirst(hb, &qb);
			FreeNode(qb);
			qa = NextPos(*Pa, ha);
			qb = NextPos(*Pb, hb);
			break;
		case -1:
			DelFirst(hb, &qb);
			InsFirst(ha, qb);
			Pa->len ++;
			qb = NextPos(*Pb, hb);
			qa = NextPos(*Pa, ha);
		}
	}
	if (Pb->len)
		Append(Pa, qb);
	FreeNode(hb);
}


void SubractPolyn(polynomail *Pa, polynomail *Pb)
{
	Link ha, hb;
	Position qa, qb;
	ElemType a, b;
	float sum;

	ha = GetHead(*Pa);
	hb = GetHead(*Pb);		//获取Pa, Pb的头结点。
	qa = NextPos(*Pa, ha);
	qb = NextPos(*Pb, hb);

	while (qa && qb)
	{
		GetCurElem(qa, &a);
		GetCurElem(qb, &b);
		switch (cmp(a, b))
		{
		case 1:
			ha = qa;
			qa = NextPos(*Pa, ha);
			break;
		case 0:
			sum = a.coef - b.coef;
			if (sum != 0.0)
			{
				qa->data.coef = sum;
				ha = qa;
			}
			else
			{
				DelFirst(ha, &qa);
				if (!ha->next)
					Pa->tail = ha;
				Pa->len --;
				FreeNode(qa);
			}
			DelFirst(hb, &qb);
			FreeNode(qb);
			qa = NextPos(*Pa, ha);
			qb = NextPos(*Pb, hb);
			break;
		case -1:
			DelFirst(hb, &qb);
			qb->data.coef = - qb->data.coef;
			InsFirst(ha, qb);
			Pa->len ++;
			qb = NextPos(*Pb, hb);
			qa = NextPos(*Pa, ha);
		}
	}
	if (Pb->len)
		Append(Pa, qb);
	FreeNode(hb);
}

void ElemMulPol(polynomail *parr, polynomail *P)	//完成单项的相乘
{
	Link ele, h, p;
	ElemType mule, e;

	h = parr->head;
	p = P->head->next;
	DelFirst(h, &ele);	//取出单个相乘的元素
	if (!h->next)
			parr->tail = h;
		parr->len --;
	mule.coef = ele->data.coef;
	mule.expn = ele->data.expn;
	FreeNode(ele);
	while (p)
	{
		e.coef = mule.coef * p->data.coef;
		e.expn = mule.expn + p->data.expn;
		MakeNode(&ele, e);
		Append(parr, ele);
		p = p->next;
	}
	PritPolyn(*parr);
}

void MultiplyPolyn(polynomail *Pa, polynomail *Pb)
{
	polynomail* Parr;
	int i, len;
	Link  h, p;

	len = Pb->len;
	h = Pb->head;
	Parr = (polynomail *) malloc(len * sizeof(polynomail));
	for (i = 0; i < len; ++i)
	{
		InitList(Parr + i);
		DelFirst(h, &p);
		if (!h->next)
			Pb->tail = h;
		Pb->len --;
		if(!p)
			printf("MultiplyPolyn error in for\n");
		Append(Parr + i, p);
	}
	for(i = 0; i < len; ++i)
	{
		ElemMulPol(Parr + i, Pa);
	}
	for(i = 0; i < len; ++i)
		AddPolyn(Pb, Parr + i);
}


